
// 分割回文串
class Solution {
public:
    int minCut(string s) {
        // 使用动态规划来实现
        int n = s.size();
        vector<vector<bool>> dp(n,vector<bool>(n));  // dp[i][j] 表示[j , i]是否是回文串

        for(int i = 0 ;i < n ; i++)
        {
            for(int j = 0 ; j <= i ; j++)
            {
                if(s[i] == s[j] && (i == j || j + 1 == i || dp[i - 1][j + 1]))
                    dp[i][j] = true;
            }
        } 
        
        // 再使用一个DP来实现 , 其中dp[i] 表示以i位置为结尾的最小划分次数
        vector<int> step(n,INT_MAX);
        step[0] = 0;
        if(dp[0][n-1]) return 0;
        for(int i = 1 ; i < n ; i++)
        {
            for(int j = 0  ;  j <= i ; j++)
            {
                if(dp[i][j] && j == 0) 
                {
                    step[i] = 0;
                    break;
                }
                if(dp[i][j]) step[i] = min(step[i], step[j-1] + 1);
            }
        }

        return step[n-1];
    }
};